U.S. Pat. No. 6,510,488 of Lasser entitled “Method For Fast Wake-Up of a Flash Memory System” discloses a method and system for allowing a flash memory system to achieve a fast wake-up time after powering it up even if the flash system software relies on management tables whose generation from scratch is time-consuming. This fast wake-up time is achieved without sacrificing data integrity. The aforementioned patent of Lasser is incorporated by reference for all purposes as if fully set forth herein.
As explained in Lasser, using flash memory devices for computer data storage traditionally requires some software translation layer that sits between the host computer's operating system and the device low-level access routines. This is so because the flash technology has some usage limitations, which make it impossible to access it in a simple random-access linear method. One such limitation is the inability to randomly overwrite any desired memory location. Therefore, the writing of new content into a flash memory location may require first erasing the whole block containing that location (preserving the contents of any other locations still needed), and only then writing the new content.
The translation layer presents to the hosting operating system a virtual view of a random-access addressable array of independent data sectors, while hiding and handling the details of mapping those virtual addresses into their real locations in the flash media. This translation mechanism is far from trivial, and an example of such a flash memory translation layer is disclosed in Amir Ban's U.S. Pat. No. 5,937,425, which is incorporated as if fully set forth herein. Ban discloses a method for implementing a mapping mechanism between virtual and physical flash addresses. Another example of such as system is detailed in U.S. Pat. No. 6,678,785, which is also incorporated as if fully set forth herein.
The translation process relies on internal translation tables that provide the flash system software with the information required for converting the host computer data access requests to the actual flash access requests. These translation tables are constructed by the software during system wake-up (or at later time, if so requested by the hosting software), based on control information stored within the flash device. Even though it is theoretically possible not to construct such tables and instead to use only the raw control data from the flash, this is practically unusable as the response time to an access request would be too slow. This is so because accessing data on flash is much slower than accessing data in regular computer RAM memory, and also because the memory tables are usually optimized for efficiency in the type of operations required during runtime, while the flash-stored control data is not.
For example, a flash physical unit might contain the number of the virtual unit mapped to it. During program runtime we may frequently need to translate a virtual unit number into its physical counterpart. If we have to rely only on flash-stored control data, we may need to scan all units until we find one with the specified virtual unit number, a very long process by the standards of a simple media access. However, by scanning the flash device once on system wake-up and constructing a table mapping each virtual unit number into a corresponding physical unit number, we are able to later do such mappings very efficiently.
The problem is that scanning the flash data storage device on system wake-up might take a long time, especially for high capacity devices. This is especially annoying for systems and devices in which a user expects immediate turn-on (i.e. cellular phones, PDAs, etc.). Simply storing the tables in the flash may work for read-only devices, such as flash devices storing only computer executable code, which is not changeable by the user. However, merely storing the tables in flash will not succeed when using devices used to store data which might be changing frequently (such as text files or spreadsheets in a PDA). This is so because when continuously writing to the device and changing its contents, the contents of the translation tables also change. It is not practical to update the copy of the tables in the flash each time they change in memory, because the incurred overhead will slow the system considerably. Consequently, a difference will be accumulated between the tables stored in flash and the “correct” ones in memory. Now if the user switches the power off and then turns it back on, without updating the tables, the software will read incorrect translation tables from flash, and the results might be data loss when writing new data.
According to some embodiments disclosed in Lasser, this problem may be solved by storing translation tables in the flash and adding some means for the software to invalidate the translation tables in a way that is detectable whenever reading them. Possible implementations (but not the only implementations) include adding a checksum value that makes the sum of all entries equal some fixed known value, or adding a validity flag to the stored tables. Additionally, one should ask the application software to call a specific function in the translation layer before shutting the system down.
In these ways the flash memory device is able to initiate fast wake-ups when the system undergoes an orderly shut down, and reverts to regular wake-ups when the system undergoes an un-orderly shut down.
While this solution is useful for many cases, there are situations where this solution may not be adequate. A first example where the solution may not be adequate is where sudden power failures are frequent and it is expected that many (or even most) of the power-up events will encounter invalid stored tables and will result in regular wake-ups that are slow.
A second example where the solution may not be adequate is where the operating system of the appliance hosting the flash memory system does not provide the software application with a service for orderly dismounting or shutting down. While complex operating systems like Linux do provide such service, there are many simpler and smaller operating systems that are designed for starting up the storage system upon power-on and never shut it down. In such cases the methods of Lasser will result in every power-up of the system doing a regular wake-up of the flash management system, gaining nothing from those methods.
A third example where the solution may not be adequate is where there is a strict limit on the length of the time interval between powering the system up and having it ready for operation. So even if power failures are rare and almost all power-up cases result in a fast wake-up of the flash management system, it is still unacceptable that a power failure will cause a later regular power-up sequence, regardless of how rare this occurs.
For the purpose of this disclosure, the term “block” is defined as the smallest unit of the flash memory that can be erased in a single operation. The term “page” is defined as the smallest unit of flash memory that can be written (also called “programmed”) in a single operation. Typically, a block contains many pages.
For the purpose of this disclosure, the terms “flash management system” and “flash file system” are synonyms and may be used interchangeably. Each of these terms refers to a software module that manages the storage of data in a flash memory device, regardless whether the interface exported by the module is file-oriented (with commands like “open file” or “write file”) or block-oriented (with commands like “read block” or “write block”), and regardless whether the software module runs on a controller dedicated solely for flash management or on the same host computer on which the applications using the storage system are running.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method and system that can always guarantee a fast wake-up of the flash memory system, without compromising the integrity of the flash data structures.